// 散列是一种常用的数据存储技术,散列后的数据可以快速地插入或取用。
// 散列使用的数据 结构叫做散列表。
// 在散列表上插入、删除和取用数据都非常快,但是对于查找操作来说却 效率低下,比如查找一组数据中的最大值和最小值。
// 这些操作得求助于其他数据结构,二 叉查找树就是一个很好的选择。

function print(x) {
    console.log(x);
}
(function () {
    function HashTable() {
        this.table = new Array(137);
        this.simpleHash = simpleHash;
        this.betterHash = betterHash;
        this.showDistro = showDistro;
        this.put = put;
        //this.get = get;
    }

    /**
     * 这个实现由碰撞
     * @param data
     * @returns {number}
     */
    function simpleHash(data) {
        var total = 0;
        for (var i = 0; i < data.length; ++i) {
            total += data.charCodeAt(i);
        }
        print("Hash value: " + data + " -> " + total);
        return total % this.table.length;
    }

    /**
     * 书上说这个算法不会碰撞,但David和Jonathan还是碰撞了
     * @param string
     * @returns {Number}
     */
    function betterHash(string) {
        const H = 37;
        var total = 0;
        for (var i = 0; i < string.length; ++i) {
            total += H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length - 1;
        }
        print("Hash value: " + string + " -> " + total);
        return parseInt(total);
    }

    function put(data) {
        var pos = this.betterHash(data);
        this.table[pos] = data;
    }

    function showDistro() {
        var n = 0;
        for (var i = 0; i < this.table.length; ++i) {
            if (this.table[i] != undefined) {
                print(i + ": " + this.table[i]);
            }
        }
    }

    var someNames = ["David", "Jennifer", "Donnie", "Raymond",
        "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];

    var hTable = new HashTable();
    for (var i = 0; i < someNames.length; ++i) {
        hTable.put(someNames[i]);
    }
    hTable.showDistro();
}());

//---------------开链法---------------------------------------------
//实现开链法的方法是:在创建存储散列过的键值的数组时,通过调用一个函数创建一个新的空数组,
// 然后将该数组赋给散列表里的每个数组元素。

(function () {
    function HashTable() {
        this.table = new Array(137);
        this.simpleHash = simpleHash;
        this.betterHash = betterHash;
        this.showDistro = showDistro;
        this.put = put;
        this.buildChains = buildChains;
        //this.get = get;
    }

    /**
     * @param data
     * @returns {number}
     */
    function simpleHash(data) {
        var total = 0;
        for (var i = 0; i < data.length; ++i) {
            total += data.charCodeAt(i);
        }
        print("Hash value: " + data + " -> " + total);
        return total % this.table.length;
    }

    /**
     * @param string
     * @returns {Number}
     */
    function betterHash(string) {
        const H = 37;
        var total = 0;
        for (var i = 0; i < string.length; ++i) {
            total += H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length - 1;
        }
        print("Hash value: " + string + " -> " + total);
        return parseInt(total);
    }

    function buildChains() {
        for (var i = 0; i < this.table.length; ++i) {
            this.table[i] = new Array();
        }
    }

    function showDistro() {
        var n = 0;
        for (var i = 0; i < this.table.length; ++i) {
            if (this.table[i][0] != undefined) {
                print(i + ": " + this.table[i]);
            }
        }
    }

    function put(data) {
        var pos = this.betterHash(data);
        var index = 0;
        if (this.table[pos][index] == undefined) {
            this.table[pos][index] = data;
            ++index;
        } else {
            while (this.table[pos][index] != undefined) {
                ++index;
            }
            this.table[pos][index] = data;
        }
        // console.log(this.table[pos][index + 1])
        console.log(index);
    }

    var hTable = new HashTable();
    hTable.buildChains();
    var someNames = ["David", "Jennifer", "Donnie", "Raymond",
        "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
    for (var i = 0; i < someNames.length; ++i) {
        hTable.put(someNames[i]);
    }
    hTable.showDistro();
}());


//-------------线性探测法----------------------------------------
//开放 寻址散列。当发生碰撞时,线性探测法检查散列表中的下一个位置是否为空。
// 如果为空, 就将数据存入该位置;如果不为空,则继续检查下一个位置,直到找到一个空的位置为 止。
// 该技术是基于这样一个事实:每个散列表都会有很多空的单元格,可以使用它们来存 储数据。
(function () {
    function HashTable() {
        this.table = new Array(137);
        this.simpleHash = simpleHash;
        this.betterHash = betterHash;
        this.showDistro = showDistro;
        this.put = put;
        this.values = [];
        //this.get = get;
    }

    /**
     * @param data
     * @returns {number}
     */
    function simpleHash(data) {
        var total = 0;
        for (var i = 0; i < data.length; ++i) {
            total += data.charCodeAt(i);
        }
        print("Hash value: " + data + " -> " + total);
        return total % this.table.length;
    }

    /**
     * @param string
     * @returns {Number}
     */
    function betterHash(string) {
        const H = 37;
        var total = 0;
        for (var i = 0; i < string.length; ++i) {
            total += H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length - 1;
        }
        print("Hash value: " + string + " -> " + total);
        return parseInt(total);
    }

    function buildChains() {
        for (var i = 0; i < this.table.length; ++i) {
            this.table[i] = new Array();
        }
    }

    function showDistro() {
        var n = 0;
        for (var i = 0; i < this.table.length; ++i) {
            if (this.table[i] != undefined) {
                print(i + ": " + this.table[i]);
            }
        }
    }

    function put(data) {
        var pos = this.betterHash(data);
        if (this.table[pos] == undefined) {
            this.table[pos] = data;
            this.values[pos] = data;
        } else {
            while (this.table[pos] != undefined) {
                pos++;
            }
            this.table[pos] = data;
            this.values[pos] = data;
        }
    }

    var hTable = new HashTable();
    var someNames = ["David", "Jennifer", "Donnie", "Raymond",
        "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
    for (var i = 0; i < someNames.length; ++i) {
        hTable.put(someNames[i]);
    }
    hTable.showDistro();
}());